partiels/100604S2/partiel_Mathsdis_S2_juin 2010.tex

   1 \documentclass[12pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage{dsfont}
  10 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  11 \usepackage[dvips]{graphics}
  12 \usepackage{epsfig}
  13 \usepackage{calc}
  14 \usepackage{tabls}
  15 \usepackage{slashbox}
  16 \usepackage{times}
  17 \usepackage{multicol}
  18 \usepackage{tabularx}
  19 \usepackage{textcomp}
  20 \usepackage{pst-all}
  21 \usepackage[a4paper]{geometry}
  22 \input{symboles.sty}
  23
  24 \geometry{hmargin=1cm, vmargin=1.5cm}
  25 \title{Département d'informatique, partiel de Mathématiques discrètes\\
  26 Semestre 2, juin 2010, 3 heures.\\
  27 }
  28
  29 \date{}
  30
  31 \begin{document}
  32 \vspace{-7em}
  33 \maketitle
  34 \vspace{-5em}
  35
  36 \noindent Seule une fiche manuscrite RV de format A5 est autorisée.
  37
  38 \section{QCM}
  39 Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ \\
  40
  41
  42 Q. 1. La négation de
  43 $(\forall x \, . \, p(x) \Rightarrow q(x))$ est
  44 $\exists x \, . \, p(x) \land \neg q(x)$.
  45  L'assertion proposée est vraie ou fausse?
  46
  47
  48 Q. 2.
  49 Soit $P$, $Q$ et $R$ des variables propositionnelles.
  50 La formule $P \land (\neg P \lor R) \land Q $ est en CNF.
  51 L'assertion proposée est vraie ou fausse ?
  52
  53 Q. 3.
  54 Soit $x$ et $y$ des entiers naturels.
  55 $\forall x \, .\, (\exists y \, .\, x +y \ge x +1 )$
  56 est vraie.
  57 L'assertion proposée est vraie ou fausse ?
  58
  59 Q. 4.
  60 Dans la formule
  61 $(\forall x \, . \, x \ge 5) \land (\exists y \, . \, y \ge x)$
  62 toutes les occurrences de la variable $x$ sont liées.
  63 L'assertion proposée est vraie ou fausse ?
  64
  65 Q. 5.
  66 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
  67 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
  68 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
  69 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
  70 et
  71 \textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre.
  72
  73 Les formules
  74 $
  75 \exists x \, .\, dodec(x) \land petit(x) \textrm{ et }
  76 \exists x \, .\, dodec(x) \Rightarrow petit(x)
  77 $
  78 n'ont jamais la même valeur de vérité.
  79  L'assertion proposée est vraie ou fausse?
  80
  81
  82 Q. 6.
  83 Une formule propositionnelle est en CNF
  84 si elle est exprimée comme une conjonction de formules.
  85 L'assertion proposée est vraie ou fausse ?
  86
  87 Q. 7. La formule
  88 $\forall x\,.\, (\exists y\,.\, p(x) \land p(y))$ est équivalente à
  89 $\forall y\,.\, (\exists x\,.\, p(y) \land p(x))$.
  90  L'assertion proposée est vraie ou fausse?
  91
  92
  93 Q. 8.
  94 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
  95 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
  96 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
  97 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
  98 et
  99 \textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre.
 100 Dans la formule suivante toutes les occurrences de $x$ sont liées.
 101 $
 102 \forall x \, . \,
 103 \textit{dodec}(x) \lor  devant(x, y) \Rightarrow
 104 (
 105 (\exists y \, .\, cube(y) \land \neg devant(x, y))
 106 \land  entre(u,y,x)
 107 ).
 108 $
 109  L'assertion proposée est vraie ou fausse?
 110
 111
 112 Q. 9.
 113 Dans la formule
 114 $P(a) \Rightarrow Q(a)$ toutes les occurrences de
 115 la variable $a$ ne sont pas liées.
 116 L'assertion proposée est vraie ou fausse ?
 117
 118 Q. 10.
 119 Soit $p(x)$ et $r(x)$ deux prédicats unaires. Une forme prénexe de
 120 $\exists x \,.\, p(x) \land (\forall y \,.\, p(y) \Rightarrow r(x))$ est
 121 $\exists x\,.\, \forall y \, . \, p(x) \land (\neg p(y) \lor r(x))$.
 122 L'assertion proposée est vraie ou fausse ?
 123
 124 Q. 11.
 125
 126 Une \emph{clause propositionnelle} est une disjonction de proposition.
 127 L'assertion proposée est vraie ou fausse ?
 128
 129
 130 Q. 12.
 131 Soit $P$, $Q$ et $R$ des variables propositionnelles.
 132 La mise en forme CNF de la formule
 133 $P \land Q \Rightarrow R$ est $\{\neg P \lor \neg Q \lor  R\}$.
 134 L'assertion proposée est vraie ou fausse ?
 135
 136 Q. 13. On se donne les prédicats suivants avec leur signification:
 137 $g(x)$ si et seulement si $x$ est un gourmet,
 138 $n(x)$ si et seulement si $x$ est généreux,
 139 $o(x)$ si et seulement si $x$ est mon oncle.
 140 \og Des gourmets manquent de générosité \fg{} peut se représenter par $\forall x \, .\, g(x) \land \neg n(x)$.
 141 L'assertion proposée est vraie ou fausse ?
 142
 143 Q. 14. On se donne les prédicats suivants avec leur signification:
 144 $g(x)$ si et seulement si $x$ est un gourmet,
 145 $n(x)$ si et seulement si $x$ est généreux,
 146 $o(x)$ si et seulement si $x$ est mon oncle.
 147 \og Mes oncles sont généreux \fg{} peut se représenter par $\exists x \, .\, g(x) \land n(x)$.
 148 L'assertion proposée est vraie ou fausse ?
 149
 150 Q. 15.
 151 Une \emph{clause propositionnelle} est une disjonction de variables
 152 propositionnelles éventuellement niées.
 153 L'assertion proposée est vraie ou fausse ?
 154
 155 Q. 16. Si j'étudie, je n'échoue pas en maths,
 156 si je ne joue pas au basket-ball, alors j'étudie,
 157 mais j'ai échoué en mathématiques.
 158 Donc, j'ai joué au basket-ball.
 159  Le raisonnement proposé est-il incorrect?
 160
 161
 162 Q. 17. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 163
 164 \begin{center}
 165 \begin{tabular}{|r|l|}
 166 \hline
 167  prédicat & sens \\
 168 \hline
 169 $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 170 $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 171 $\textit{femme}(x)$                  & $x$ est une femme \\
 172 $\textit{homme}(x)$                  & $x$ est un  homme \\
 173 $\textit{fidele}(x)$                 & $x$ est fidèle \\
 174 $\textit{honete}(x)$                 & $x$ dit la vérité \\
 175 $a$                                  & Alice \\
 176 $b$                                  & Bob \\
 177 $c$                                  & Clinton \\
 178 \hline
 179 \end{tabular}
 180 \end{center}
 181
 182 \og Chaque époux aime son épouse et réciproquement \fg{} peut se  traduire en
 183 $
 184 \forall x,y \, . \,
 185 (\textit{homme}(x) \land
 186 \textit{femme}(y) \land
 187 \textit{maries}(x,y)) \Rightarrow
 188 (\textit{aime}(x,y) \land
 189 \textit{aime}(y,x))
 190 $.
 191 L'assertion proposée est vraie ou fausse ?
 192
 193 Q. 18. La négation de
 194 $(\forall x \, . \, p(x) \Rightarrow q(x))$ est
 195 $\exists x \, . \, \neg p(x) \Rightarrow \neg q(x)$.
 196  L'assertion proposée est vraie ou fausse?
 197
 198
 199 Q. 19. On se donne les prédicats suivants avec leur signification:
 200 $g(x)$ si et seulement si $x$ est un gourmet,
 201 $n(x)$ si et seulement si $x$ est généreux,
 202 $o(x)$ si et seulement si $x$ est mon oncle.
 203 \og Des gourmets manquent de générosité \fg{} peut se représenter par $\forall x \, .\, g(x) \Rightarrow \neg n(x)$.
 204 L'assertion proposée est vraie ou fausse ?
 205
 206 Q. 20.
 207 Soit $a$ et $b$ des symboles de constante,
 208 $f$ un symbole de fonction unaire,
 209 $g$ un symbole de fonction binaire et
 210 $S$ un symbole de relation binaire.
 211 L'expression $g(a,f(b))$ contient quatre termes.
 212  L'assertion proposée est vraie ou fausse ?
 213
 214
 215 Q. 21.
 216 La négation de
 217 $(\exists y \, . \, p(y) \land \neg q(y))$ est
 218 $(\forall y \, . \, \neg p(y) \lor \neg   q(y))$.
 219  L'assertion proposée est vraie ou fausse?
 220
 221 Q. 22. On se donne les prédicats suivants avec leur signification:
 222 $g(x)$ si et seulement si $x$ est un gourmet,
 223 $n(x)$ si et seulement si $x$ est généreux,
 224 $o(x)$ si et seulement si $x$ est mon oncle.
 225 \og Certains de mes oncles ne sont pas gourmets \fg{} peut se représenter par $\forall x \, .\, o(x) \Rightarrow \neg g(x)$.
 226 L'assertion proposée est vraie ou fausse ?
 227
 228 Q. 23.  On considère la proposition
 229 $$
 230   (A \Rightarrow B) \Rightarrow
 231   ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
 232 $$
 233 Il existe une démonstration syntaxique sous hypothèses
 234   qui prouve que cette proposition est un théorème. L'assertion proposée est vraie ou fausse ?
 235
 236
 237 Q. 24.
 238 Une \emph{clause propositionnelle} est une conjonction de variables
 239 propositionnelles éventuellement niées.
 240 L'assertion proposée est vraie ou fausse ?
 241
 242 Q. 25.
 243
 244 Soit $p(x)$ et $q(x)$ deux prédicats unaires. Une forme prénexe de
 245 $(\forall x \,.\, p(x)) \Rightarrow \exists x \,.\, q(x)$ est
 246 $\forall x\,.\, (\exists x  \, . \, p(x) \Rightarrow q(x))$.
 247 L'assertion proposée est vraie ou fausse ?
 248
 249
 250
 251 Q. 26.
 252 Soit $p(x)$ et $q(x)$ deux prédicats unaires. Une forme prénexe de
 253 $(\forall x \,.\, p(x)) \Rightarrow \exists x \,.\, q(x)$ est
 254 $\exists x \, . \, \neg p(x) \lor q(x)$.
 255 L'assertion proposée est vraie ou fausse ?
 256
 257 Q. 27.
 258 Soit $P$, $Q$ et $R$ des variables propositionnelles.
 259 La mise en forme CNF de la formule
 260 $(P \Rightarrow Q) \land (P \Rightarrow R)$ est $\{\neg P \lor Q , \neg P \lor R\}$.
 261 L'assertion proposée est vraie ou fausse ?
 262
 263 Q. 28. Si je travaille, je ne peux pas étudier;
 264 Soit je travaille, soit je suis reçu en mathématiques;
 265 j'ai été reçu en mathématiques.
 266 Donc j'ai étudié.
 267  Le raisonnement proposé est-il incorrect?
 268
 269
 270 Q. 29. Dans la formule
 271 $(\forall x\,.\, p(x) \Rightarrow q(x)) \land r(y)$, la variable
 272 $x$ admet une occurrence libre.
 273  L'assertion proposée est vraie ou fausse?
 274
 275
 276 Q. 30. La négation de
 277 $(\exists y \, . \, p(y) \land \neg q(y))$ est
 278 $(\forall y \, . \, \neg p(y) \lor  q(y))$.
 279  L'assertion proposée est vraie ou fausse?
 280
 281
 282 Q. 31. La formule
 283 $\forall x \,.\, x > 0 \Rightarrow
 284   (\exists y \, . \, e^y = x )
 285 $
 286 est vraie sur l'univers $\mathds{R}$.
 287 L'assertion proposée est vraie ou fausse ?
 288
 289 Q. 32.
 290 Soit $p(x)$ et $r(x)$ deux prédicats unaires. Une forme prénexe de
 291 $\forall x \,.\, (\forall y \,.\, p(y)) \Rightarrow r(x)$ est
 292 $\forall x, y  \, . \, p(y) \lor \neg r(x)$.
 293 L'assertion proposée est vraie ou fausse ?
 294
 295 Q. 33.
 296 Un ensemble de clauses est contradictoire par résolution s'il existe une paire de clauses
 297 dont la résolvante est la clause vide.
 298 L'assertion proposée est vraie ou fausse ?
 299
 300 Q. 34.
 301 Les formules $P\lor \neg Q \lor R$ et $ \neg P \lor Q \lor \neg R$ sont résolubles.
 302 L'assertion proposée est vraie ou fausse ?
 303
 304 Q. 35. Soit $p(x)$ le prédicat unaire qui est vrai si et seulement
 305 si le paramètre $x$ est pair.
 306 La formule
 307 $
 308 (\exists x \, . \, p(x))
 309 \Rightarrow
 310 (\forall x \, . \, p(x))
 311 $ est vraie sur l'univers $\{1 \}$.
 312 L'assertion proposée est vraie ou fausse?
 313
 314 Q. 36.
 315 Soit $P$, $Q$ et $R$ des variables propositionnelles.
 316 La mise en forme CNF de la formule
 317 $P \Rightarrow (Q \land R)$ est $\{\neg P \lor Q ,R\}$ .
 318 L'assertion proposée est vraie ou fausse ?
 319
 320 Q. 37.  Soit $P$, $Q$ et $R$ des variables propositionnelles.
 321 La formule
 322 $ P \lor Q \lor \neg R$
 323 est une clause propositionnelle.
 324 L'assertion proposée est vraie ou fausse ?
 325
 326 Q. 38.
 327 Soit \textit{dodec} le prédicat unaire qui est vrai si son paramètre est un dodécaèdre,
 328 \textit{cube} le prédicat unaire qui est vrai si son paramètre est un cube,
 329 \textit{petit} le prédicat unaire qui est vrai si son paramètre est petit,
 330 \textit{entre} le prédicat ternaire qui est vrai si son premier paramètre est entre le second et le troisième
 331 et
 332 \textit{devant} le prédicat binaire qui est vrai si son premier paramètre est devant son second paramètre.
 333 \og les seuls grands cubes sont b et c \fg{} peut-elle se traduire en
 334 $
 335 \forall x \, .\,
 336 (\neg petit(x) \land cube(x))
 337 \leftrightarrow
 338  ( x = b \lor  x = c).
 339 $
 340  L'assertion proposée est vraie ou fausse?
 341
 342
 343 Q. 39.
 344 Les formules $P\lor \neg Q \lor R$ et $ P \lor  Q$ sont résolubles.
 345 L'assertion proposée est vraie ou fausse ?
 346
 347 Q. 40.
 348 Si la saturation de la résolution engendre la clause vide, alors l'ensemble de clauses est satisfaisable.
 349 L'assertion proposée est vraie ou fausse ?
 350
 351 % Q. 41. On se donne les prédicats suivants avec leur signification:
 352 % $g(x)$ si et seulement si $x$ est un gourmet,
 353 % $n(x)$ si et seulement si $x$ est généreux,
 354 % $o(x)$ si et seulement si $x$ est mon oncle.
 355 % \og Des gourmets manquent de générosité \fg{} peut se représenter par $\exists x \, .\, g(x) \land \neg n(x)$.
 356 % L'assertion proposée est vraie ou fausse ?
 357
 358 % Q. 42. La négation de
 359 % $(\exists y \, . \, p(y) \land \neg q(y))$ est
 360 % $(\forall y \, . \, p(y) \Rightarrow  q(y))$.
 361 %  L'assertion proposée est vraie ou fausse?
 362
 363
 364 % Q. 43.
 365 % Une formule propositionnelle est en (CNF)
 366 % si elle est exprimée comme une disjonction de clauses.
 367 % L'assertion proposée est vraie ou fausse ?
 368
 369 % Q. 44. On considère les prédicats et constantes suivants avec leur interprétation sur un univers constitué d'individus humains.
 370
 371 % \begin{center}
 372 % \begin{tabular}{|r|l|}
 373 % \hline
 374 %  prédicat & sens \\
 375 % \hline
 376 % $\textit{aime}(x,y)$                 & $x$ aime $y$ \\
 377 % $\textit{maries}(x,y)$                & $x$ et $y$ sont mariés  \\
 378 % $\textit{femme}(x)$                  & $x$ est une femme \\
 379 % $\textit{homme}(x)$                  & $x$ est un  homme \\
 380 % $\textit{fidele}(x)$                 & $x$ est fidèle \\
 381 % $\textit{honete}(x)$                 & $x$ dit la vérité \\
 382 % $a$                                  & Alice \\
 383 % $b$                                  & Bob \\
 384 % $c$                                  & Clinton \\
 385 % \hline
 386 % \end{tabular}
 387 % \end{center}
 388
 389 % \og L'époux qui aime son épouse lui est fidèle \fg{} peut se traduire en
 390 % $
 391 % \forall x,y \, . \,
 392 % \textit{homme}(x) \land
 393 % \textit{femme}(y) \land
 394 % \textit{maries}(x,y) \land
 395 % \textit{aime}(x,y) \land
 396 % \textit{aime}(y,x)
 397 % $.
 398 % L'assertion proposée est vraie ou fausse ?
 399
 400 % Q. 45.
 401 % Soit $P$, $Q$ et $R$ des variables propositionnelles.
 402 % La mise en forme CNF de la formule
 403 % $P \land Q \Rightarrow R$ est $\{\neg P, \neg Q, R\}$ .
 404 % L'assertion proposée est vraie ou fausse ?
 405
 406 % Q. 46.  Soit $P$, $Q$ et $R$ des variables propositionnelles.
 407 % La formule
 408 % $ P \lor Q \lor (P \land \neg R)$
 409 % est une clause propositionnelle.
 410 % L'assertion proposée est vraie ou fausse ?
 411
 412 % Q. 47. La relation $\{P,Q\} \vdash R$   se lit-elle
 413 % \og $R$ est une conséquence logique de l'ensemble
 414 %                      $\{P,Q\}$ \fg{}?
 415
 416
 417 \section*{Réponses au QCM}
 418 \begin{Large}
 419 \begin{center}
 420 \begin{tabular}{|l|c|c||l|c|c||l|c|c|}
 421 \hline
 422 Numéro & V & F & Numéro & V & F & Numéro & V & F \\
 423 \hline
 424 Q. 1 & &  & Q. 2 & &  & Q. 3 & &  \\
 425 \hline
 426 Q. 4 & &  & Q. 5 & &  & Q. 6 & &  \\
 427 \hline
 428 Q. 7 & &  & Q. 8 & &  & Q. 9 & &  \\
 429 \hline
 430 Q. 10 & &  & Q. 11 & &  & Q. 12 & &  \\
 431 \hline
 432 Q. 13 & &  & Q. 14 & &  & Q. 15 & &  \\
 433 \hline
 434 Q. 16 & &  & Q. 17 & &  & Q. 18 & &  \\
 435 \hline
 436 Q. 19 & &  & Q. 20 & &  & Q. 21 & &  \\
 437 \hline
 438 Q. 22 & &  & Q. 23 & &  & Q. 24 & &  \\
 439 \hline
 440 Q. 25 & &  & Q. 26 & &  & Q. 27 & &  \\
 441 \hline
 442 Q. 28 & &  & Q. 29 & &  & Q. 30 & &  \\
 443 \hline
 444 Q. 31 & &  & Q. 32 & &  & Q. 33 & &  \\
 445 \hline
 446 Q. 34 & &  & Q. 35 & &  & Q. 36 & &  \\
 447 \hline
 448 Q. 37 & &  & Q. 38 & &  & Q. 39 & &  \\
 449 \hline
 450 Q. 40 & &  &  & &  &  & &  \\
 451 \hline
 452 \end{tabular}
 453 \end{center}
 454 \end{Large}
 455 \section{Raisonnement}
 456
 457 \subsection{Preuve syntaxique par résolution}
 458 Effectuer la preuve syntaxique suivante par résolution:
 459 $$
 460 \left\{
 461 A \Rightarrow B \lor C,
 462 D \Rightarrow A,
 463 B \Rightarrow \neg D\right\}
 464 \big) \vdash
 465 D \Rightarrow C
 466 $$
 467
 468 \subsection{L'Île de Puro Pira}
 469 L'île de Puro Pira est peuplée
 470 de \emph{Purs} qui disent toujours la vérité et de
 471 de \emph{Pires} qui ne disent que des mensonges.
 472
 473 Débarqué sur l'île, l'anthropologue Abercrombie rencontre trois indigènes Alice, Bernard et Chloé.
 474 \begin{enumerate}
 475 \item\label{item1} Alice affirme \og C’est moi le chef\fg{}.
 476 \item\label{item2} Bernard affirme aussi \og C’est moi le chef\fg{}.
 477 \item Quant à Chloé elle ajoute \og Au plus l’un de nous trois dit la vérité.\fg{}
 478 \end{enumerate}
 479 On sait qu'il n'y a qu'un seul chef.
 480
 481 Par la suite
 482 \begin{itemize}
 483 \item $A$, $B$ et $C$ sont les variables propositionnelles qui valent chacune
 484   vrai si et seulement si $A$ est un pur,   $B$ est un pur et $C$ est un pur respectivement;
 485 \item $Ac$, $Bc$ et $Cc$ sont les variables propositionnelles qui
 486   valent chacune vrai si et seulement si $Ac$ est un chef,   $Bc$ est un chef
 487   et $Cc$ est un chef respectivement;
 488 \end{itemize}
 489
 490
 491 \begin{enumerate}
 492 \item Montrer que l'affirmation \og il n'y a qu'un seul chef \fg{}
 493   peut se représenter par la formule
 494   $$ (Ac \lor Bc \lor Cc) \land
 495   \neg (Ac \land Bc) \land \neg (Ac \land Cc) \land \neg (Bc \land Cc)
 496   $$
 497 \item Montrer que l'affirmation de Chloé peut se représenter par la formule
 498   $$
 499   (C \Rightarrow \neg A \land \neg B ) \land
 500   (\neg C \Rightarrow A \land B )
 501   $$
 502 \item Traduire en logique propositionnelle les propositions des
 503   items~\ref{item1}. et~\ref{item2} relatives aux affirmations d'Alice et
 504   Bernard.
 505 \item A l'aide de la méthode de résolution trouver le statut de chaque
 506 indigène.
 507 \end{enumerate}
 508
 509
 510 \subsection{Problème Bonus}
 511  On considère les propositions suivantes:\par
 512 \begin{enumerate}
 513 \item  Tout crime a un auteur
 514 \item Seuls les gens malhonnêtes commettent des crimes
 515 \item  On n'arrête que les gens malhonnêtes
 516 \item  Les gens malhonnêtes arrêtés ne commettent pas de crimes
 517 \item  Des crimes se produisent
 518 \end{enumerate}
 519
 520 Montrer par la méthode de votre choix qu'il y a
 521 des gens malhonnêtes en liberté.
 522
 523
 524 \end{document}